Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
Кафедра АПЕПС
Алгоритмізація та програмування - 2. Процедурне програмування
ЗВІТ
до лабораторної роботи № 3
«Списки»
Варіант № 18
Дата «10» червня 2022
ЗАВДАННЯ:
1. Дослідити особливості створення одно- та дво-направлених списків.
2. Вивчити і реалізувати механізми додавання нових записів у список, пошуку записів у списку за певними полями, видалення записів зі списку та редагування знайдених записів, а також збереження всього списку у файлі та зчитування списку із файлу до пам’яті з відновленням всіх зв’язків.
3. Розробити Блок-схему програмного алгоритму.
4. Оформити ЗВІТ до лабораторної роботи згідно вимог та методичних рекомендацій.
РЕЗУЛЬТАТ РОБОТИ:
1. Роздрукувати (вивести на екран) попередньо сформовані та підготовлені для запису в файл дані.
2. Роздрукувати (вивести на екран) результат виконання операції читання даних із файлу.
3. ЗВІТ до комп’ютерного практикуму для перевірки додати в Клас.
4. Програмний код (відкритий для редагування) розмістити на сайті Repl.it (посилання виключно через кнопку «+Invite »).
Теоретичні відомості:
Елемент списку є складовою (структурованою) змінною, що містить збережені дані і покажчики на сусідів:
struct elem { // визначення структурованого типу
int value; // значення елемента (збережені дані)
elem *next; // єдиний покажчик
//elem *next,*prev; // два покажчика
elem *links[10]; // обмежена кількість покажчиків (максимум 10) //elem **plinks; // довільна кількість покажчиків
};
Як видно з прикладу, змінна такого типу може містити одну, дві, не більше 10 і довільну (динамічний масив) кількість вказівників на аналогічні змінні. Але це ще не список, а опис його складових (елементів) як типу даних. З нього випливає тільки, що кожен з них посилається на аналогічні елементи. Ніяк не можна визначити ні кількості таких змінних в структурі даних, ні характеру зв’язків між ними (послідовний, циклічний, довільний).
Отже, конкретний тип структури даних (лінійний список, дерево, граф) залежить від функцій, які з нею працюють.
Залежно від зв’язків списки бувають наступних видів:
• однозв’язні – кожен елемент списку має покажчик на наступний;
• двозв’язні – кожен елемент списку має покажчик на наступний і на попередній елементи;
• циклічні – перший і останній елементи списку посилаються один на одного і ланцюжок представляє собою кільце.
Звідси ж випливає, що звичайні (розімкнуті) списки мають в якості обмежувача послідовності NULL-покажчик. Відповідно, можливий випадок пустого списку, в якому заголовок – покажчик на перший елемент також містить значення NULL.
Бінарне дерево – це впорядковане дерево, кожна вершина якого має не більше двох піддерев, причому для кожного вузла виконується правило: в лівому піддереві містяться тільки ключі, що мають значення, менші, ніж значення даного вузла, а в правому піддереві містяться тільки ключі, що мають значення, більші, ніж значення даного вузла.
Дерево складається з гілок (вузлів) і листя (елементів). Листя – це вузли, які не вказують ні на кого, у них немає гілочок. Бінарне дерево – це дерево, в якому у гілки може бути не більше двох листів або гілок. Звідси і його назва – «бінарне», тобто елементів два або менше. Але ніяк не більше двох.
Розглянемо структуру, що описується як динамічний список: Поле даних і два покажчика на праву і ліву гілки. У динамічних списках два покажчика зазвичай пов’язують наступний і попередній елементи, у випадку з деревом цього не знадобиться, оскільки, як правило, прохід по дереву йде з кореня. Хоча звичайно ж може бути і зворотний зв’язок.
struct Branch
{
char Data;
Branch *LeftBranch;
Branch *RightBranch;
};
Поле Data представляє дані, на підставі яких будується дерево. Точніше один з елементів даних. Поля Branch описують ліву і праву гілки дерева, і є покажчиками на таку ж структур...
